public class MinWeightTriangulation {
    /**
     * 凸多边形最优三角剖析，利用动态规划求解
     * @param args
     */
/*
题目说明：
设A是顶点为0，1，…，n-1的n凸多边形，可以用不在内部相交的n-3条对角线将A划分成三角形
假设凸n边形的边及对角线的长度dij，都是给定的正整数，0≤i<j≤n-1.划分后三角形ijk的权值等于其周长，
求具有最小权值的划分方案

输入：d = [
			[0,2,3,1,5,6],
			[2,0,3,4,8,6],
			[3,3,0,10,13,7],
			[1,4,10,0,12,5],
			[5,8,13,12,0,3],
			[6,6,7,5,3,0]
		  ]
输出：54

 */
//    先将对角线设置为0，然后按照节点数从小到大进行循环，计算i到j的最小权值和剖分位置。
//    在计算最小权值时需要枚举剖分点k，并计算以k为分界点的两部分的最小权值和，
//    如果小于当前的最小权值，则更新最小权值和剖分位置。
//    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+d ik+d kj+d ij);

    public static void main(String[] args) {
        int [][]d=new int[][]{
                {0,2,3,1,5,6},
                {2,0,3,4,8,6},
                {3,3,0,10,13,7},
                {1,4,10,0,12,5},
                {5,8,13,12,0,3},
                {6,6,7,5,3,0}
        };

        MinWeightTriangulation minWeightTriangulation = new MinWeightTriangulation();
        System.out.println(minWeightTriangulation.minWeight(d));
    }

    public int minWeight(int[][] d){
        int[][] dp=new int[d.length][d[0].length];
        for(int i=d.length-1;i>=0;i--){
            for(int j=0;j<d[0].length;j++){
                if(j-i==1){
                    dp[i][j]=0;
                    continue;
                }
                dp[i][j]=Integer.MAX_VALUE;
                for(int k=i+1;k<j;k++){
                    dp[i][j]=Math.min(dp[i][j],dp[i][k] + dp[k][j] + d[i][k] + d[k][j] + d[i][j]);
                }
            }
        }
        return dp[0][dp[0].length-1];
    }

}
